package com.Algorithm.Study.LinkedList;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2021/10/13/8:17
 * @Description:在链表类中实现这些功能：
 *
 * get(index)：获取链表中第index个节点的值。如果索引无效，则返回-1。
 * addAtHead(val)：在链表的第一个元素之前添加一个值为val的节点。插入后，新节点将成为链表的第一个节点。
 * addAtTail(val)：将值为val 的节点追加到链表的最后一个元素。
 * addAtIndex(index,val)：在链表中的第index个节点之前添加值为val 的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
 * deleteAtIndex(index)：如果索引index 有效，则删除链表中的第index 个节点。
 *
 * @Target: 自建链表,并且要求实现基本功能! ---- 定义!-->初始化-->先查-->增-->删
 */
public class MyLinkedList {


// 定义结构
    // 链表结构: 需要的---节点:(值,next)
    class Node {  // 节点
        int val; // 值
        Node next; // 下一个链表

        Node(int val) {  // 链表对象构造器
            this.val = val;
        }
    }



// 初始化!!!
        int size;   // 长度.判断末尾
        Node head;   // 链表必有一个头节点 head(head,next)
        /** Initialize your data structure here. */
        public MyLinkedList() {  // init  初始化(1.长度,2.头指针)
            this.size = 0;
            this.head = null;
        }





// 查!get
        /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
        public int get(int index) {
            if (index < 0 || index >= size || head == null) {
                return -1;
            }
            Node temp = this.head;
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
            return temp.val;
        }




        /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
        public void addAtHead(int val) {
            Node node = new Node(val);
            node.next = this.head;
            this.head = node;
            size++;
        }

        /** Append a node of value val to the last element of the linked list. */
        public void addAtTail(int val) {
            if (size == 0) {     // size==0就是增加头节点
                this.head = new Node(val);
                head.next = null;
                size++;
            }else {
                Node temp = this.head;    // 从head开始跑
                while (temp.next != null) {  // 找到末尾节点
                    temp = temp.next;
                }
                Node tail = new Node(val);  // 新建节点,,也就是尾节点
                tail.next = null;   // 尾节点的next指向null
                temp.next = tail;   // 旧节点的next指向尾节点
                size++;   // 长度增加
            }
        }

        /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
        public void addAtIndex(int index, int val) {  // 增加中间节点(位置,值)
            if (index > this.size) {  // 如果index>链表长度,就直接不通过,中断
                return;
            }
            if (index <= 0) {   // 如果index<=0 使用头节点增加  然后中断
                addAtHead(val);
                return;
            }
            if (index == this.size) {  // index等于长度 使用尾节点增加 然后中断
                addAtTail(val);
                return;
            }

            Node temp = this.head;
            for (int i = 0; i < index - 1; i++) {
                temp = temp.next;
            }
            Node insertNode = new Node(val);
            insertNode.next = temp.next;
            temp.next = insertNode;
            size++;
        }

        /** Delete the index-th node in the linked list, if the index is valid. */
        public void deleteAtIndex(int index) {
            if (index < 0 || index >= this.size) {  // <0    >=长度
                return;
            }
            if (index == 0) {  // 头节点删除 --head--newhead(Node2)-------------
                if (size != 1) {  // 除头之外有其它,头节点的下一个要成为头节点..Node temp = this.head.next ;  this.head = temp;
                    Node temp = this.head.next; // 先使用一个临时Node获取头的下一个
                    this.head =temp;        // 头等于临时        // this.head = this.head.next;
                    size--;
                    return;
                }else {   // 只有头节点
                    this.head = null;
                    size--;
                    return;
                }
            }
            Node temp = this.head;
            for (int i = 0; i < index - 1; i++) {
                temp = temp.next;
            }
            Node deleteNode = temp.next;
            temp.next = deleteNode.next;
            size--;
        }
    }
/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
